from typing import Optional


class Node:
    # 提高访问属性的速度，并节省内存
    __slots__ = 'prev', 'next', 'key', 'value'
    def __init__(self, key = 0, value = 0):
        self.key = key
        self.value = value

# 时间复杂度：所有操作均为 O(1)。
# 空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。
class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dummy = Node() # 哨兵节点
        self.dummy.prev = self.dummy
        self.dummy.next = self.dummy
        self.cache = {}

    def get_node(self, key: int) -> Optional[Node]:
        if key not in self.cache:
            return None
        node = self.cache[key]
        self.removeNode(node)
        self.addTohead(node)
        return node

    # 获取 key 对应的节点，同时把该节点移到链表头部
    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    """
    方法：从缓存中获取键对应的值，如果键存在则将其移动到链表头部表示最近使用

    Args:
        key: 要获取值的键

    Returns:
        如果键存在返回对应的值，否则返回-1

    Time: O(1)

    Space: O(1)
    """

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:
            node.value = value #存在则更新值
            return
        self.cache[key] = node = Node(key, value)
        self.addTohead(node)
        if len(self.cache) > self.capacity: #容量超出
            lastNode = self.dummy.prev
            del self.cache[lastNode.key]
            self.removeNode(lastNode)

    # 删除一个节点
    def removeNode(self, x: Node) -> None:
        x.prev.next = x.next
        x.next.prev = x.prev
    
    def addTohead(self, x: Node) -> Node:
        x.prev = self.dummy
        x.next = self.dummy.next
        x.prev.next = x
        x.next.prev = x

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)